package com.zyk.grate_offer.class11;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangsan
 * @date 2021/5/30 18:29
 */
public class Code01_MinInsertionStepToPalindromeString {

    // 暴力解
    public static int minNum(String str) {
        return f(str.toCharArray(), 0, str.length() - 1);
    }

    // L~R范围是回文串, 最少需要添加多少个字符
    public static int f(char[] str, int L, int R) {
        if (L > R) return 0;
        int p1 = Integer.MAX_VALUE;
        if (str[L] == str[R]) {
            p1 = f(str, L + 1, R - 1);
        }
        int p2 = 1 + f(str, L + 1, R);
        int p3 = 1 + f(str, L, R - 1);
        return Math.min(p1, Math.min(p2, p3));
    }

    // 暴力解改dp, 范围尝试的模型
    public static int minNum2(String s) {
        char[] str = s.toCharArray();
        int N = str.length;
        int[][] dp = new int[N][N];
        // 依赖左下角, 下边, 左边
        // r: L, c: R
        for (int r = N - 2; r >= 0; --r) {
            for (int c = r + 1; c < N; ++c) {
                dp[r][c] = Math.min(dp[r][c - 1] + 1, dp[r + 1][c] + 1);
                if (str[r] == str[c]) {
                    dp[r][c] = Math.min(dp[r][c], dp[r + 1][c - 1]);
                }
            }
        }
        return dp[0][N - 1];
    }

    // 返回最少添加的一种情况
    public static String minInsertionResult(String s) {
        char[] str = s.toCharArray();
        int N = str.length;
        int[][] dp = new int[N][N];
        for (int r = N - 2; r >= 0; --r) {
            for (int c = r + 1; c < N; ++c) {
                dp[r][c] = Math.min(dp[r][c - 1] + 1, dp[r + 1][c] + 1);
                if (str[r] == str[c]) {
                    dp[r][c] = Math.min(dp[r][c], dp[r + 1][c - 1]);
                }
            }
        }
        char[] res = new char[N + dp[0][N - 1]];
        int l = 0, r = res.length - 1;
        int i = 0, j = N - 1;
        // dfs, 取一个结果就行
        while (i <= j) {
            if (str[i] == str[j]) {  // i+1 ~j-1
                res[l++] = str[i++];
                res[r--] = str[j--];
            } else {
                // 取左边或下边找到 = dp[i][j] - 1 的路
                if (dp[i + 1][j] == dp[i][j] - 1) {  // 下边也就是 i+1 ~ j
                    res[r--] = str[i];
                    res[l++] = str[i];
                    i++;
                } else {     // i ~ j-1
                    res[l++] = str[j];
                    res[r--] = str[j];
                    j--;
                }
            }
        }

        return new String(res);
    }

    // 返回所有最少添加的情况
    public static List<String> minInsertionAllResult(String s) {
        char[] str = s.toCharArray();
        int N = str.length;
        int[][] dp = new int[N][N];
        for (int r = N - 2; r >= 0; --r) {
            for (int c = r + 1; c < N; ++c) {
                dp[r][c] = Math.min(dp[r][c - 1] + 1, dp[r + 1][c] + 1);
                if (str[r] == str[c]) {
                    dp[r][c] = Math.min(dp[r][c], dp[r + 1][c - 1]);
                }
            }
        }
        char[] path = new char[N + dp[0][N - 1]];
        List<String> ans = new ArrayList<>();
        dfs(dp, ans, 0, N - 1, 0, path.length - 1, path, str);
        return ans;
    }

    public static void dfs(int[][] dp, List<String> list, int i, int j, int l, int r, char[] path, char[] str) {
        if (i > j) {
            list.add(new String(path));
            return;
        }

        if (str[i] == str[j]) {  // i+1 ~j-1
            path[l] = str[i];
            path[r] = str[j];
            dfs(dp, list, i + 1, j - 1, l + 1, r - 1, path, str);
        }

        // 取左边或下边找到 = dp[i][j] - 1 的路
        if (dp[i + 1][j] == dp[i][j] - 1) {  // 下边也就是 i+1 ~ j
            path[r] = str[i];
            path[l] = str[i];
            dfs(dp, list, i + 1, j, l + 1, r - 1, path, str);
        }
        if(dp[i][j-1] == dp[i][j]-1){     // i ~ j-1
            path[l++] = str[j];
            path[r--] = str[j];
            dfs(dp, list, i, j - 1, l + 1, r - 1, path, str);
        }
    }


    public static void main(String[] args) {
        String str = "qweqweqweqassada";
        System.out.println(minNum(str));
        System.out.println(minNum2(str));
        System.out.println(minInsertionResult(str));
        System.out.println(minInsertionAllResult(str));
    }

}
